1. Field of the Invention
This specification relates to computer technologies, and, more particularly, to systems and methods for performing fast, large scale, high-dimensional searches.
2. Description of the Related Art
Finding nearby points among a large set in high dimensions is at the heart of many important applications. These applications include, for example, nearest neighbor classification, similarity search, and feature matching, to name a few.
For instance, consider an image matching application where an input image is compared against a large database of stored images in order to find a match. Each image may be represented by “descriptors,” such as scale-invariant feature transform (“SIFT”) descriptors, Speeded Up Robust Features (“SURF”) descriptors, global image feature (“GIST”) descriptors, or the like. In a typical case, each image may have tens or hundreds of descriptors, and each descriptor may in turn contain hundreds or thousands of dimensions or features. In this type of environment, finding a match invariably involves performing one or more large scale, high-dimensional searches.
Despite prolonged study, the problem of efficiently finding nearby points in high dimensions remains open. This long-standing difficulty in finding an exact nearest neighbor in high dimensions has led to the use of approximate algorithms, as well as domain-specific approaches. Recently, image and video retrieval have been the subject of numerous practical applications. For video retrieval tasks, for example, the number of points to search is usually much larger than can be held in a computer system's memory. This has led to the development of certain compressed representations, each being typically custom-designed for a specific application.
Mathematically, search problems may be generically posed as follows. First, consider a finite set of points X⊂n. |X|=N|, drawn from the probability distribution p(x) defined over n, where n| refers to an n-dimensional space with real coordinates. Point proximity may then be determined by a metric d(x, x′), where x is a query point and x′ is a point in a database. In this context, two fundamental proximity queries are known as Radial and Nearest-k. A Radial search returns a set of points within a given radius of a query, whereas a Nearest-k search classifies an object based on closest training examples within n└.
One approach to the search problem involves hash-based retrieval. Hash-based retrieval may include performing a quantization operation followed by a look-up operation based on the quantized representation. Quantization aims to identify a unique partition containing x within a finite partitioning of n└, whereas an index look-up attempts to return all x′εX contained within the given partition. This technique may be used for near-duplicate search, where one can rely on a hash collision even when the representation includes of a large number of bits. However, for proximity searches, such as Radial and Nearest-k, hash-based retrieval becomes ineffective as the sparseness of the code space increases.